package HuaweiMeeting;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Test2 {
    /**
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     *
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 示例 1:
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     *
     * 示例 2:
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     *
     * 提示：
     * 1 <= k <= nums.length <= 104
     * -104 <= nums[i] <= 104
     */
    public static void main(String[] args) {
        int[] arr = {3,2,1,5,6,4};
        System.out.println(findK2(arr, 2));
    }
    public static int findK(int[] arr, int k) {
        if (arr.length == 0 || k > arr.length || k == 0) return -1;
        quickSort(0, arr.length - 1, arr);
        return arr[arr.length - k];
    }
    public static int findK2(int[] arr, int k) {
        if (arr.length == 0 || k > arr.length || k == 0) return -1;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : arr) {
            if (queue.size() < k) {
                queue.add(num);
            }else {
                if (num > queue.peek()) {
                    queue.poll();
                    queue.add(num);
                }
            }
        }
        return queue.poll();
    }
    public static void quickSort(int start, int end, int[] arr) {
        if (start >= end) return;
        int l = start, r = end, pivot = arr[start];
        while (l < r) {
            while (l < r && arr[r] >= pivot) r--;
            arr[l] = arr[r];
            while (l < r && arr[l] <= pivot) l++;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        quickSort(start, l - 1, arr);
        quickSort(l + 1, end, arr);
    }
}
